普通的求一个最长上升子序列，一个最大下降子序列，输出就OK了，是n^2的复杂度
而这样就过不了300000的点了
所以我们就用二分查找的办法来优化，因为输入的复杂度无法优化，所以复杂度是nlogn
最长上升子序列上升思路：
有一个low数组，low[i]是长度为i的最长子序列的最小值
维护一个上升序列，如果加入的数>low[len],最长子序列就可以更新了，如果小于等于，则把正好大于他的一个数改为他。这样就可以用最小数的更新最长子序列了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int m,n;
int f[309999],f2[309999],h[309999]; int a[30999],low[399999];int len,len2,low2[399999];
int maxn=-9999;int t;int j;int p;int u;
int find(int x){
int l=1,r=len;
while(l<=r)
{
int mid=(l+r)>>1;
if(low[mid]<h[x]) l=mid+1;
else r=mid-1;
}
return l;
}//二分背的板子。。。
int find2(int x){
int l=1,r=len2;
while(l<=r)
{
int mid=(l+r)>>1;
if(low2[mid]>=h[x]) l=mid+1;
else r=mid-1;
}
return l;
}
int main()
{
while(++t&&~scanf("%d",&h[t]));
low[1]=h[1];
len=1;
for(int i=2;i<t;i++)
{
if(low[len]<h[i])
{
low[++len]=h[i];
}
else {
int w=find(i);
low[w]=h[i];
}
}
low2[1]=h[1];
len2=1;
for(int i=2;i<t;i++)
{
if(low2[len2]>=h[i])
{
low2[++len2]=h[i];
}
else {
int w=find2(i);
low2[w]=h[i];
}
}printf("%d\n",len2);
printf("%d",len);
}